#include <iostream>
#include <queue>
#include <utility>
#include <cstdlib>

// struture of a threaded binary tree node
typedef struct TBNode{
    int data;
    TBNode *LChild;
    TBNode *RChild;
	// flags, 0 for thread, 1 for pointer
	bool leftFlag;
	bool rightFlag;
}TBNode,*TBTree;

void initTree(TBTree &tree);
void getTree(TBTree &tree);
void Level_Order(TBTree &tree);
void makeThread(TBTree &node, TBTree &pre);
void setDummy(TBTree &tree);
TBNode *getPrior(TBNode *node);
TBNode *getNext(TBNode *node);

int main() {
    // the number of the test sets
    int T = 0;
    std::cin >> T;
    for (int i = 0; i < T; i++) {
    	TBTree tree = new TBNode;
		TBNode* dummy = new TBNode;
        initTree(tree);
        getTree(tree);
        TBNode* pre = NULL;
        makeThread(tree,pre);
        setDummy(tree);
        Level_Order(tree);
    }
}

// Initialize the tree
void initTree(TBTree &tree) {
    tree->data = 0;
    tree->LChild = 0;
	tree->leftFlag = 0;
    tree->RChild = 0;
	tree->rightFlag = 0;
}

// get the nodes of the tree in level order
void getTree(TBTree &tree) {
    int key = 0;
    std::cin >> key;
    tree->data = key;
    TBNode* node = tree;
    std::queue<TBNode*> que;
    que.push(node);
    
    while(!que.empty()) {
        node = que.front();
        node->LChild = new TBNode;
        node->RChild = new TBNode;
        que.pop();

        std::cin >> key;
        if(key != 0){
            que.push(node->LChild);
            // If the left pointer points to a child
            // Set the left flag to 1
			node->leftFlag = 1;
            node->LChild->data = key;
        }
        else if (key == 0) {
            // If the left pointer points to a thread
            // Set the left flag to 0
			node->leftFlag = 0;
        	node->LChild = NULL;
		}
            
        std::cin >> key;
        if(key != 0){
            que.push(node->RChild);
            // If the right pointer points to a child
            // Set the right flag to 1
			node->rightFlag = 1;
            node->RChild->data = key;
        }
        else if (key == 0) {
            // If the right pointer points to a thread
            // Set the right flag to 0
			node->rightFlag = 0;
        	node->RChild = NULL;
		}
    }
    std::cin>>key;
    return;
}

// Print the result in level order
void Level_Order(TBTree &tree) {
    TBNode* node = tree;
    std::queue<TBNode*> que;
    que.push(node);
    
    while(!que.empty()) {
        node = que.front();
        que.pop();

        // find and print the predecessor
        if(node->leftFlag != 0){
            que.push(node->LChild);
            std::cout << getPrior(node)->data << " ";
        }
        else if (node->leftFlag == 0) {
        	std::cout << getPrior(node)->data << " ";
		}
            
        // find and print the successor
        if(node->rightFlag != 0){
            que.push(node->RChild);
            std::cout << getNext(node)->data << " ";
        }
        else if (node->rightFlag == 0){
        	std::cout << getNext(node)->data << " ";
		}
    }
    std::cout << "\n";
    return;
}

// Add threads to the tree
void makeThread(TBTree &node, TBTree &pre) {
    if (node) {
        makeThread(node->LChild, pre);
        if (node->LChild == NULL) {
            node->LChild = pre;
        }
        if (pre && pre->RChild == NULL) {
            pre->RChild = node;
        }
        pre = node;
        makeThread(node->RChild, pre);
    }
    return;
}

// Create a dummy node
// Make the left most and the right most point to dummy
void setDummy(TBTree &tree) {
	TBNode* dummy = new TBNode;
	dummy->data = 0;
	dummy->leftFlag = 1;
	dummy->rightFlag = 1;
	dummy->LChild = tree;
	dummy->RChild = dummy;
	TBTree p = tree;
	while(p->leftFlag != 0)
		p = p->LChild;
	p->LChild = dummy;
	
	p = tree;
	while(p->rightFlag != 0)
		p = p->RChild;
	p->RChild = dummy;
}

// Find the predecessor
TBNode *getPrior(TBNode *node) { 
	// If the leftFlag is 0, the thread is the predecessor
    if(node->leftFlag == 0) 
		return(node->LChild);
	// Otherwise, find the right most of the left child
	TBNode* pre = node->LChild;
	while(pre->rightFlag != 0)
		pre = pre->RChild;
	return(pre);
}

// Find the successor
TBNode *getNext(TBNode *node)
{ 
    // If the rightFlag is 0, the thread is the successor
	if(node->rightFlag == 0) 
		return(node->RChild);
	TBNode* next = node->RChild;
	// Otherwise, find the left most of the right child
	while(next->leftFlag != 0)
		next=next->LChild;
	return(next);
}